Pallister có trận ra mắt đội B tuyển Anh vào tháng 5 năm 1989; anh bắt đầu trận đấu với Thụy Sĩ trước khi bị thay thế bởi Alan McLeary trong trận thắng 2−0 tại Stadion Schützenwiese [9]. Anh ra sân thêm tám lần nữa trong ba năm tiếp theo với lần cuối cùng là chiến thắng 3−0 trước Pháp vào tháng 2 năm 1992.[9]

Pallister có trận ra mắt đội tuyển Anh trong trận giao hữu với Hungary vào tháng 4 năm 1988.[10]. Anh chơi cả trận trong trận hòa không bàn thắng tại Népstadion ở Budapest. [11] Gary đã phải đợi hơn ba năm để được ra mắt thi đấu khi anh ấy chơi trong trận thắng Thổ Nhĩ Kỳ tại vòng loại UEFA Euro 1992.[10][11] Pallister đủ điều kiện tham dự vòng chung kết giải đấu tại Thụy Điển tuy nhiên anh đã không có tên trong danh sách 23 cầu thủ dự vòng chung kết [12]. Anh đã góp mặt ở US Cup vào tháng 6 năm 1993;[10] Gary được đá chính ngay từ đầu trong 2 thất bại trước Hoa Kỳ [13] và Đức,[14] cùng trận hòa với Selecao ở lượt cuối,[15] kết thúc giải đấu, "Tam Sư" đứng ở vị trí cuối bảng.[16] Pallister đã chơi ba trận khi đội tuyển Anh không vượt qua vòng loại FIFA World Cup 1994 [10][17]. Gary Pallister không được ra sân thường xuyên trong ba năm sau đó, chủ yếu chơi trong các trận giao hữu, trước khi có lần cuối cùng ở vòng loại FIFA World Cup 1998 gặp Moldova và Ba Lan vào mùa thu năm 1996 [10][18][19]. Sau cùng, Pallister đã có 22 lần khoác áo đội tuyển và không ghi được bàn thắng nào [10].